/**
 * //每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成
 * //了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon
 * //是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
 * //
 * // 在结果列表中，选择 字典序最小 的名字作为真实名字。
 * //
 * //
 * //
 * // 示例：
 * //
 * //
 * //输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"],
 * //synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
 * //输出：["John(27)","Chris(36)"]
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // names.length <= 100000
 * //
 * //
 * // Related Topics 深度优先搜索 广度优先搜索 并查集 数组 哈希表 字符串 计数 👍 52 👎 0
 */

package com.xixi.basicAlgroithms.disJointSet;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ID_interview_17_07_BabyNamesLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_17_07_BabyNamesLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> rootCount = new HashMap<>();

        public String[] trulyMostPopular(String[] names, String[] synonyms) {

            //0. 初始化并查集元素，因为names中的名字不一定包含在synonyms中
            for (String name : names) {
                int i = 0;
                while (name.charAt(i) != '(') i++;
                parent.put(name.substring(0, i), name.substring(0, i));
            }

            //1. 生成Hash表，名称对应的并查集
            for (String synonym : synonyms) {
                String[] synonymNames = synonym.split(",");
                String firstName = synonymNames[0].substring(1, synonymNames[0].length()); //Jon
                String secondName = synonymNames[1].substring(0, synonymNames[1].length() - 1); //John

                //synonyms中的名字也不一定包含在names中
                if (!parent.containsKey(firstName)) parent.put(firstName, firstName); //默认自己是自己的根
                if (!parent.containsKey(secondName)) parent.put(secondName, secondName); //默认自己是自己的根

                //获取两个名字的根
                String firstNameP = find(firstName);
                String secondNameP = find(secondName);

                if (!firstNameP.equals(secondNameP)) { //如果不是同一棵树，要做合并
                    if (firstNameP.compareTo(secondNameP) > 0) { //firstNameP比secondNameP字典序大，secondNameP就是firstNameP的爹
                        parent.put(firstNameP, secondNameP);
                    } else {//反之亦然
                        parent.put(secondNameP, firstNameP);
                    }
                }


            }

            //2. 合并计数
            for (String name : names) {
                int i = 0;
                while (name.charAt(i) != '(') i++;
                String root = find(name.substring(0, i));
                //root累加所有值
                rootCount.put(root, rootCount.getOrDefault(root, 0) + Integer.parseInt(name.substring(i + 1, name.length() - 1)));
            }


            List<String> result = new ArrayList<>(rootCount.size());

            //3. 输出
            for (Map.Entry<String, Integer> entry : rootCount.entrySet()) {
                result.add(entry.getKey() + "(" + entry.getValue() + ")");
            }

            return result.toArray(new String[result.size()]);

        }

        //查根
        public String find(String child) {
            if (!parent.get(child).equals(child)) { //如果不是刚刚初始化的名字
                parent.put(child, find(parent.get(child))); //就将自己根的根合并到这条树上来。//补全操作
            }

            return parent.get(child);

        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}